package company.tree;

import java.util.Scanner;

/**
 * 700. 二叉搜索树中的搜索
 * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
 * <p>
 * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
 * <p>
 *  
 * <p>
 * 示例 1:
 * 输入：root = [4,2,7,1,3], val = 2
 * 输出：[2,1,3]
 * 示例 2:
 * <p>
 * <p>
 * 输入：root = [4,2,7,1,3], val = 5
 * 输出：[]
 */
public class SearchBST700 {
    static TreeNode root;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split("\\s+");
        String[] nodes = input[0].replace("[", "").replace("]", "")
                .replace("\\s+", "").split(",");
        String childNode = input[1].replace("\\s+", "");

        // 根节点不能放在packBinaryTree里面设置，因为每个节点插入时候，是需要
        root = new TreeNode(Integer.parseInt(nodes[0]));
        packBinaryTree(root, nodes);
        TreeNode treeNode = searchBST(root, Integer.parseInt(childNode));
        if (null == treeNode) {
            System.out.println("[]");
        } else {
            System.out.println("[" + treeNode.getValue() + "," + treeNode.getLeft().getValue() + "," +
                    treeNode.getRight().getValue() + "]");
        }
    }

    // 非递归方式 知道根节点，配置子节点
    private static TreeNode packBinaryTree(TreeNode treeNode, String[] nodes) {
        int len = nodes.length;
        for (int i = 1; i < len; i++) {
            treeNode = root;
            while (treeNode != null) {
                TreeNode left = treeNode.getLeft();
                TreeNode right = treeNode.getRight();
                int val = Integer.parseInt(nodes[i]);
                TreeNode childNode = new TreeNode(val);
                if (val < treeNode.getValue()) {
                    if (left == null) {
                        treeNode.setLeft(childNode);
                        break;
                    }
                    treeNode = left;
                } else {
                    if (right == null) {
                        treeNode.setRight(childNode);
                        break;
                    }
                    treeNode = right;
                }
            }
        }
        return treeNode;
    }

    public static TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        while (root != null) {
            if (root.getValue() == val) {
                return root;
            }
            if (val < root.getValue()) {
                root = root.getLeft();
            } else {
                if (val > root.getValue()) {
                    root = root.getRight();
                }
            }
        }
        return root;
    }
}

